package 回溯.排列;
import java.util.List;
import java.util.Deque;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Arrays;
public class leetcode46全排列系列 {


	public List<List<Integer>> permuteUnique(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		boolean [] flag = new boolean[nums.length];
		Arrays.sort(nums);
		recursion(0,nums,ans,path,flag);
		return ans;
	}
	// 不用这个 index 参数也是 可以的 ， 直接 使用  path，size（） 进行计数 也是一样的！
	// 这个 index 参数 纯粹 是 为了 计数的
	public void recursion(int index,int nums[],List<List<Integer>> ans,Deque<Integer> path,boolean []flag){
		if(index == nums.length){
			// 别忘了 这种集合间转换的方式
			ans.add(new ArrayList<>(path));
			return ;
		}
		for(int i = 0;i < nums.length; i++){
			// 去重
			if( flag[i] ||  i >  0 && nums[i] == nums[i - 1] && !flag[i - 1]){ //  从 同一 树层， 和 同一 树枝上面去理解， 就很好理解了！
				continue;
			}
			path.addLast(nums[i]);
			flag[i] = true;
			recursion(index + 1,nums,ans,path,flag);
			flag[i] = false;
			path.removeLast();
		}
	}








}
